#!/usr/bin/env python
# -*-coding:UTF-8-*-
from functools import reduce


def sort_func(data_list, index=0):
    """
    基于内置函数 sorted  实现排序
    """

    data_list.sort(key=lambda i: i[index], reverse=True)
    return data_list


def subset(list_var):
    # Displacement method
    result = [list_var]
    n = len(list_var)
    for i in range(1, 2**n-1):
        res = []
        for j in range(n):
            if (i >> j) % 2:
                res.append(list_var[j])
        result.append(res)
    return result


def subset1(list_var):
    # Displacement method

    result = [[list_var[0]], ]
    i = 1
    while i < len(list_var):
        lens = len(result)
        j = 0
        while j < lens:
            tmp = result[j].copy()
            tmp.append(list_var[i])
            result.append(tmp)
            j += 1
        result.append(list_var[i:i+1])
        i += 1
    return result


def bag1(good, wth_max):
    subset_id = subset(range(len(good)))
    good1 = []
    for item in subset_id:
        wth_sum = sum([good[x][3] for x in item])
        if wth_sum <= wth_max:
            val_sum = sum([good[x][2] for x in item])
            good1.append([item, val_sum, wth_sum])
    good2 = sort_func(good1, index=1)[0:1]
    return good2


def bag2(n, c, w, v):
    """
    n  物品的数量，
    c 书包能承受的重量，
    w 每个物品的重量，
    v 每个物品的价值
    """

    value = [[0 for j in range(c + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, c + 1):
            value[i][j] = value[i - 1][j]
            # 背包总容量够放当前物体，遍历前一个状态考虑是否置换
            if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
                value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
    return value


def show(n, c, w, value):
    print('最大价值为:', value[n][c])
    x = [False for i in range(n)]
    j = c
    for i in range(n, 0, -1):
        if value[i][j] > value[i - 1][j]:
            x[i - 1] = True
            j -= w[i - 1]
    print('背包中所装物品为:')
    for i in range(n):
        if x[i]:
            print('第', i+1, '个,', end='')


def main():
    good = [[0, 'computer', 200, 20],
            [1, 'radio', 20, 4],
            [2, 'clock', 175, 10],
            [3, 'vase', 50, 2],
            [4, 'book', 10, 1],
            [5, 'Oil Painting', 90, 9]
            ]
    wth_max = 20
    good1 = bag1(good, wth_max)
    for item in good1:
        print('good:  %-30s' % ', '.join([good[x][1] for x in item[0]]), end=' '*5)
        print('value: %d' % item[1], end=' '*5)
        print('wigth: %d' % item[2], )

    good2 = bag2(6, 20, [20, 4, 10, 2, 1, 9], [200, 20, 175, 50, 10, 90])
    show(6, 20, [20, 4, 10, 2, 1, 9], good2)


if __name__ == '__main__':
    main()
    '''
    逻辑上没有太大的问题，就是print的时候，考虑下format的
    '''